/*
https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/submissions/570842885/
在d天内送达包裹的能力
二分
*/
class Solution {
public:
    bool check(vector<int>& weights,int mid, int days)
    {
        int ws = 0;
        int d = 1;
        for(auto x:weights)
        {
            if(ws + x > mid)
            {
                d++;
                ws = 0;
            } 
            ws += x;
            if(d > days) return false;
        }
        return true;
    }
    int shipWithinDays(vector<int>& weights, int days) {
        int left = 0;
        int right = 0;
        for(auto x:weights)
        {
            left = max(x,left);
            right += x;
        }
        while(left < right)
        {
            //int mid = left+(right-left) / 2;
            int mid = (left+right) >> 1;
            if(check(weights,mid,days))
            {
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return right;
    }
};